package com.gitee.ty850454.leetcode224;

import java.util.Arrays;

/**
 * 基本计算器
 *
 * 实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。
 *
 * 示例 1：
 * 输入：s = "1 + 1"
 * 输出：2
 *
 * 示例 2：
 * 输入：s = " 2-1 + 2 "
 * 输出：3
 *
 * 示例 3：
 * 输入：s = "(1+(4+5+2)-3)+(6+8)"
 * 输出：23
 *
 * 提示：
 * 1 <= s.length <= 3 * 105
 * s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
 * s 表示一个有效的表达式
 *
 * 思考：
 * 这题看似有一堆括号，存在优先级问题，但是因为只有加减法，所以其实还是从左向右计算，如果括号外是加法，无视括号，如果括号外是减法，括号内算法结果取反
 * 针对括号可以嵌套以及存在多组的情况，增加栈，每个括号是一个单独的、完整的计算单元，拥有自己的总符号，进入一个计算单元时，将它的符号压栈，退出计算单元时，符号弹栈
 *
 * @author xy
 */
public class Leetcode224 {

    public static void main(String[] args) {
        Leetcode224 instance = new Leetcode224();
        // System.out.println(instance.calculate("1 + 1"));
        System.out.println(instance.calculate(" 2-1 + 2"));
        System.out.println(instance.calculate("12-1+22"));
        System.out.println(instance.calculate("2-(1+2)-(2-2)"));
        // System.out.println(instance.calculate("(1+(4+5+2)-3)+(6+8)"));
        // System.out.println(instance.calculate("1+2-(3-(2-3))"));
    }

    public int calculate(String s) {
        char[] chars = s.toCharArray();

        // 当前符号，正号是1，负号是-1，便于相乘
        int sign = 1;

        // 保存符号的栈
        IntStack stack = new IntStack(chars.length);
        stack.push(sign);

        int result = 0;

        for (int i = 0; i < chars.length;) {
            char aChar = chars[i];
            switch (aChar) {
                case ' ':
                    i++;
                    continue;
                case '+':
                    sign = stack.peek();
                    i++;
                    continue;
                case '-':
                    sign = -stack.peek();
                    i++;
                    continue;
                case '(':
                    stack.push(sign);
                    i++;
                    continue;
                case ')':
                    stack.pop();
                    i++;
                    continue;
                default:
                    // 取数字
                    int num = aChar - '0';
                    while (++i < chars.length && Character.isDigit(aChar = chars[i])) {
                        num = num * 10 + aChar - '0';
                    }
                    result += sign * num;
            }
        }
        return result;
    }

    public static class IntStack {

        /** 栈元素数组 */
        private final int[] elements;

        /** 栈顶索引 */
        private int topIndex = -1;

        /**
         * 初始化一个栈
         *
         * @param capacity 栈容量
         */
        public IntStack(int capacity) {
            elements = new int[capacity];
        }

        /**
         * 判断栈是否为空
         *
         * @return 空栈返回true，否则返回false
         */
        boolean empty() {
            return topIndex < 0;
        }

        /**
         * 查看堆栈顶部的对象
         *
         * @return 栈顶部的对象
         */
        public int peek() {
            return elements[topIndex];
        }

        /**
         * 压栈
         *
         * @param newElement 压入的元素
         */
        public void push(int newElement) {
            elements[++topIndex] = newElement;
        }

        /**
         * 弹栈，因为本例不需要弹出的元素所以未返回弹出的元素
         */
        public void pop() {
            topIndex--;
        }

        @Override
        public String toString() {
            return Arrays.toString(elements);
        }

    }

}
